# 45/100 二叉树-二叉树的右视图
# leetcode第199题: https://leetcode.cn/problems/binary-tree-right-side-view/?envType=study-plan-v2&envId=top-100-liked
# Date: 2024/12/18
from collections import deque
from typing import Optional

from leetcode.bds import TreeNode, TreeConverter
import leetcode.test as test


def rightSideView(root: Optional[TreeNode]) -> list[int]:
    """层序遍历"""
    if not root:
        return []
    queue = deque([root])
    res = []
    while queue:
        size = len(queue)
        for i in range(size):
            curr = queue.popleft()
            if curr.left:
                queue.append(curr.left)
            if curr.right:
                queue.append(curr.right)
            if i == size - 1:
                res.append(curr.val)
    return res


def rightSideView_dfs(root: Optional[TreeNode]) -> list[int]:
    """深度优先遍历，在遍历过程中优先搜索右子树，这里不使用递归的方法，以防止栈溢出"""
    res = dict()  # 深度为索引，存放节点的值
    max_depth = -1

    stack = [(root, 0)]
    while stack:
        node, depth = stack.pop()

        if node is not None:
            # 维护二叉树的最大深度
            max_depth = max(max_depth, depth)

            # 如果不存在对应深度的节点我们才插入
            res.setdefault(depth, node.val)

            stack.append((node.left, depth + 1))
            stack.append((node.right, depth + 1))

    return [res[depth] for depth in range(max_depth + 1)]


if __name__ == '__main__':
    t1 = TreeConverter.list_to_tree([1, 2, 3, None, 5, None, 4])
    t2 = TreeConverter.list_to_tree([1, 2, 3, 4, None, None, None, 5])
    t3 = TreeConverter.list_to_tree([1, None, 3])
    t4 = TreeConverter.list_to_tree([])
    inp = [{"root": t1}, {"root": t2}, {"root": t3}, {"root": t4}, ]
    out = [[1, 3, 4], [1, 3, 4, 5], [1, 3], []]
    test.test_function(rightSideView, inp, out, times=1000)
    test.test_function(rightSideView_dfs, inp, out, times=1000)
